package Implementacion;

import util.OperacionesTDA;
import Entidades.Coordenada;
import Entidades.Plano;
import Entidades.Planta;
import Implementaciones.Cola;
import Implementaciones.Conjunto;
import Interfaces.RobotDesastresInterface;
import TDA.ColaTDA;
import TDA.ConjuntoTDA;

public class RobotDesastresImpl implements RobotDesastresInterface {

	private OperacionesTDA<Coordenada> util = new OperacionesTDA<Coordenada>();

	@Override
	public void RescatarVictimas(Plano plano,
			ConjuntoTDA<Coordenada> victimas,
			ConjuntoTDA<Coordenada> victimasRescatadas,
			ColaTDA<Coordenada> camino) {
		try {
			for(int i = 0; i < plano.ObtenerCantidadPlantas(); i++) {
				Planta planta = plano.ObtenerPlanta(i);
				ColaTDA<Coordenada> caminoEnPlanta = new Cola<Coordenada>();
				caminoEnPlanta.inicializarCola();
				caminoEnPlanta.acolar(crearCoordenada(0, 0, planta.obtenerNroPiso()));
				ConjuntoTDA<Coordenada> victimasRescatadasEnPlanta = new Conjunto<Coordenada>();
				victimasRescatadasEnPlanta.inicializarConjunto();
					
				ConjuntoTDA<Coordenada> victimasEnPlanta = obtenerVictimasEnPlanta(victimas, planta.obtenerNroPiso());
				ConjuntoTDA<ColaTDA<Coordenada>> ordenes = obtenerOrdenes(victimasEnPlanta);
				
				int maximoRescates = 0;
				
				while(!ordenes.conjuntoVacio()) {
					ColaTDA<Coordenada> orden = ordenes.elegir();
					ordenes.sacar(orden);
					
					/*
					 * Usando un socorrerPlantaSegunOrden no-recursivo
					 */
//					ColaTDA<Coordenada> caminoParcial = util.clonar(caminoEnPlanta);
//					ConjuntoTDA<Coordenada> victimasRescatadasParcial = new Conjunto<Coordenada>();
//					victimasRescatadasParcial.inicializarConjunto();					
//					socorrerPlantaSegunOrden(planta, orden, caminoParcial, victimasRescatadasParcial);
					
					/*
					 * Usando un socorrerPlantaSegunOrden recursivo
					 */
					ConjuntoTDA<Coordenada> victimasRescatadasParcial = new Conjunto<Coordenada>();
					victimasRescatadasParcial.inicializarConjunto();
					ColaTDA<Coordenada> caminoParcial = socorrerPlantaSegunOrden(planta, orden, caminoEnPlanta, victimasRescatadasParcial);					
					
					int rescates = util.longitud(victimasRescatadasParcial);
					if(rescates > maximoRescates || 
							(rescates == maximoRescates && util.longitud(caminoParcial) < util.longitud(caminoEnPlanta))) {
						maximoRescates = rescates;
						util.reemplazarElementos(caminoParcial, caminoEnPlanta);
						util.reemplazarElementos(victimasRescatadasParcial, victimasRescatadasEnPlanta);
					}
				}
				
				util.agregarElementos(caminoEnPlanta, camino);
				util.agregarElementos(victimasEnPlanta, victimasRescatadas);
			}
			for(int i = plano.ObtenerCantidadPlantas()-2; i >= 0; i--) {
				camino.acolar(crearCoordenada(0, 0, i));
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	/*
	 * socorrerPlantaSegunOrden no-recursivo
	 */
//	private void socorrerPlantaSegunOrden(Planta planta, ColaTDA<Coordenada> victimas, ColaTDA<Coordenada> camino, ConjuntoTDA<Coordenada> victimasRescatadas) {
//		
//		while(!victimas.colaVacia()) {
//			Coordenada victima = victimas.primero();
//			victimas.desacolar();
//			
//			ColaTDA<Coordenada> menorCamino = obtenerMenorCamino(planta, camino, victima);
//			
//			if(!menorCamino.colaVacia()) {	// Si encontro un camino
//				util.reemplazarElementos(menorCamino, camino);
//				victimasRescatadas.agregar(victima);
//			}
//		}
//		
//		Coordenada actual = util.obtenerUltimoElemento(camino);
//		int x = actual.obtenerPosicionX();
//		int y = actual.obtenerPosicionY();
//		for(int i = x; i> 0;i--) {
//			Coordenada c = crearCoordenada(i-1, y, planta.obtenerNroPiso());
//			camino.acolar(c);
//		}
//		for(int j = y; j> 0;j--) {
//			Coordenada c = crearCoordenada(0, j-1, planta.obtenerNroPiso());
//			camino.acolar(c);
//		}
//	}

	/*
	 * socorrerPlantaSegunOrden recursivo
	 */
	private ColaTDA<Coordenada> socorrerPlantaSegunOrden(Planta planta, ColaTDA<Coordenada> victimas, ColaTDA<Coordenada> camino, ConjuntoTDA<Coordenada> victimasRescatadas) {
		if(victimas.colaVacia()) {
			Coordenada actual = util.obtenerUltimoElemento(camino);
			int x = actual.obtenerPosicionX();
			int y = actual.obtenerPosicionY();
			for(int i = x; i> 0;i--) {
				Coordenada c = crearCoordenada(i-1, y, planta.obtenerNroPiso());
				camino.acolar(c);
			}
			for(int j = y; j> 0;j--) {
				Coordenada c = crearCoordenada(0, j-1, planta.obtenerNroPiso());
				camino.acolar(c);
			}
			return camino;
		} else {
			Coordenada victima = victimas.primero();
			victimas.desacolar();
			
			ColaTDA<Coordenada> menorCamino = obtenerMenorCamino(planta, camino, victima);
			
			if(!menorCamino.colaVacia()) {	// Si encontro un camino
				victimasRescatadas.agregar(victima);
				return socorrerPlantaSegunOrden(planta, victimas, menorCamino, victimasRescatadas);
			} else {
				return socorrerPlantaSegunOrden(planta, victimas, camino, victimasRescatadas);
			}
		}
	}

	private Coordenada crearCoordenada(int x, int y, int z) {
		Coordenada coord = new Coordenada();
		coord.setearPosicionX(x);
		coord.setearPosicionY(y);
		coord.setearNroPlanta(z);
		
		return coord;
	}
	
	private ConjuntoTDA<ColaTDA<Coordenada>> obtenerOrdenes(ConjuntoTDA<Coordenada> victimas) {
		ConjuntoTDA<ColaTDA<Coordenada>> ordenes = new Conjunto<ColaTDA<Coordenada>>();
		ordenes.inicializarConjunto();		
		ColaTDA<Coordenada> orden = new Cola<Coordenada>();
		orden.inicializarCola();
		
		obtenerOrdenes(victimas, orden, ordenes);
		
		return ordenes;
	}

	private void obtenerOrdenes(ConjuntoTDA<Coordenada> victimas,
			ColaTDA<Coordenada> orden, ConjuntoTDA<ColaTDA<Coordenada>> ordenes) {
		if(victimas.conjuntoVacio()) {
			ordenes.agregar(orden);
		} else {
			ConjuntoTDA<Coordenada> aux = util.clonar(victimas);
			while(!aux.conjuntoVacio()) {
				Coordenada victima = aux.elegir();
				aux.sacar(victima);
				
				ColaTDA<Coordenada> copiaOrden = util.clonar(orden);
				copiaOrden.acolar(victima);				
				ConjuntoTDA<Coordenada> copiaVictimas = util.clonar(victimas);
				copiaVictimas.sacar(victima);
				obtenerOrdenes(copiaVictimas, copiaOrden, ordenes);
			}
		}
	}
	
	private ColaTDA<Coordenada> obtenerMenorCamino(Planta planta, ColaTDA<Coordenada> camino, Coordenada destino) {
		ColaTDA<Coordenada> mejorCamino = new Cola<Coordenada>();
		mejorCamino.inicializarCola();
		obtenerMenorCamino(planta, destino, camino, mejorCamino);
		return mejorCamino;
	}
	
	private void obtenerMenorCamino(Planta planta, Coordenada destino, ColaTDA<Coordenada> camino, ColaTDA<Coordenada> mejorCamino) {
		Coordenada ultima = util.obtenerUltimoElemento(camino);
		if(ultima.equals(destino)) {
			if(mejorCamino.colaVacia() || (util.longitud(camino) < util.longitud(mejorCamino))) {
				util.reemplazarElementos(camino, mejorCamino);
			}
		} else {			
			int dimension = planta.obtenerDimensionPlanta();
			if(ultima.obtenerPosicionX() < (dimension - 1)) {
				int i = ultima.obtenerPosicionX() + 1;
				int j = ultima.obtenerPosicionY();
				Coordenada nueva = crearCoordenada(i, j, planta.obtenerNroPiso());
				if(planta.esAccesible(i, j) && !util.pertenece(camino, nueva)) {
					ColaTDA<Coordenada> copiaCamino = util.clonar(camino);
					copiaCamino.acolar(nueva);
					obtenerMenorCamino(planta, destino, copiaCamino, mejorCamino);
				}
			}
			if(ultima.obtenerPosicionX() > 0) {
				int i = ultima.obtenerPosicionX() - 1;
				int j = ultima.obtenerPosicionY();
				Coordenada nueva = crearCoordenada(i, j, planta.obtenerNroPiso());
				if(planta.esAccesible(i, j) && !util.pertenece(camino, nueva)) {
					ColaTDA<Coordenada> copiaCamino = util.clonar(camino);
					copiaCamino.acolar(nueva);
					obtenerMenorCamino(planta, destino, copiaCamino, mejorCamino);
				}
			}
			if(ultima.obtenerPosicionY() < (dimension - 1)) {
				int i = ultima.obtenerPosicionX();
				int j = ultima.obtenerPosicionY() + 1;
				Coordenada nueva = crearCoordenada(i, j, planta.obtenerNroPiso());
				if(planta.esAccesible(i, j) && !util.pertenece(camino, nueva)) {
					ColaTDA<Coordenada> copiaCamino = util.clonar(camino);
					copiaCamino.acolar(nueva);
					obtenerMenorCamino(planta, destino, copiaCamino, mejorCamino);
				}
			}
			if(ultima.obtenerPosicionY() > 0) {
				int i = ultima.obtenerPosicionX();
				int j = ultima.obtenerPosicionY() - 1;
				Coordenada nueva = crearCoordenada(i, j, planta.obtenerNroPiso());
				if(planta.esAccesible(i, j) && !util.pertenece(camino, nueva)) {
					ColaTDA<Coordenada> copiaCamino = util.clonar(camino);
					copiaCamino.acolar(nueva);
					obtenerMenorCamino(planta, destino, copiaCamino, mejorCamino);
				}
			}
		}
	}
	
	private ConjuntoTDA<Coordenada> obtenerVictimasEnPlanta(ConjuntoTDA<Coordenada> victimas, int nroPiso) {		
		ConjuntoTDA<Coordenada> aux = new Conjunto<Coordenada>();
		ConjuntoTDA<Coordenada> victimasEnPlanta = new Conjunto<Coordenada>();
		aux.inicializarConjunto();
		victimasEnPlanta.inicializarConjunto();		

		while (!victimas.conjuntoVacio()) {
			Coordenada coord = victimas.elegir();
			victimas.sacar(coord);
			if (coord.obtenerNroPlanta() == nroPiso) {
				victimasEnPlanta.agregar(coord);
			}
			aux.agregar(coord);
		}
		
		while (!aux.conjuntoVacio()) {
			Coordenada coord = aux.elegir();
			aux.sacar(coord);
			victimas.agregar(coord);
		}
		
		return victimasEnPlanta;
	}

}
